package gold.digger;

import java.util.Arrays;
import java.util.Stack;

/**
 * Created by fanzhenyu02 on 2020/3/1.
 */
public class LC84 {

    public int largestRectangleArea(int[] arr) {
        int res = 0;
        Stack<Integer> st = new Stack<>();
        int[] heights = Arrays.copyOf(arr, arr.length + 1);
        for (int i = 0; i < heights.length; ++i) {
            while (!st.empty() && heights[st.peek()] >= heights[i]) {
                int cur = st.pop();
                res = Math.max(res, heights[cur] * (st.empty() ? i : (i - st.peek() - 1)));
            }
            st.push(i);
        }
        return res;
    }


    public static void main(String[] args) {
        LC84 an = new LC84();
        int arr[] = {2, 1, 5, 6, 2, 3};
        System.out.println(an.largestRectangleArea(arr));
    }
}
